
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1097. -- [POI2007]旅游景点atr -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1097: [POI2007]旅游景点atr</h2><span class=green>Time Limit: </span>30 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>357 MB<br><span class=green>Submit: </span>781&nbsp;&nbsp;<span class=green>Solved: </span>125<br>[<a href='submitpage.php?id=1097'>Submit</a>][<a href='problemstatus.php?id=1097'>Status</a>][<a href='bbs.php?id=1097'>Discuss</a>]</center><h2>Description</h2><div class=content>FGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景，品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的，比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山，而是希望去另外什么地方喝下午茶。幸运的是,FGD的旅程不是既定的，他可以在某些旅行方案之间进行选择。
由于FGD非常讨厌乘车的颠簸，他希望在满足他的要求的情况下，旅行的距离尽量短，这样他就有足够的精力来欣赏风景或者是泡MM了^_^.
整个城市交通网络包含N个城市以及城市与城市之间的双向道路M条。城市自1至N依次编号，道路亦然。没有从某个城市直接到它自己的道路，两个城市之间最多只有一条道路直接相连，但可以有多条连接两个城市的路径。任意两条道路如果相遇，则相遇点也必然是这N个城市之一，在中途，由于修建了立交桥和下穿隧道，道路是不会相交的。每条道路都有一个固定长度。
在中途，FGD想要经过K(K<=N-2)个城市。成都编号为1，上海编号为N,而FGD想要经过的N个城市编号依次为2,3,…,K+1.
举例来说，假设交通网络如下图。FGD想要经过城市2,3,4,5，并且在2停留的时候在3之前，而在4,5停留的时候在3之后。那么最短的旅行方案是1-2-4-3-4-5-8,总长度为19。
注意FGD为了从城市2到城市4可以路过城市3,但不在城市3停留。这样就不违反FGD的要求了。并且由于FGD想要走最短的路径，因此这个方案正是FGD需要的。

 
</div><h2>Input</h2><div class=content>第一行包含3个整数N(2<=N<=20000),M(1<=M<=200000),K(0<=K<=20),意义如上所述。
以下M行，每行包含3个整数X，Y，Z，(1<=X<Y<=N, 1<=Z=1000)表示城市X与Y之间有一条双向道路。你可以认为输入文件使得一定能自成都到上海以及任何FGD想要去的城市。
下一行包含一个整数G(0<=G<=K*(K-1)/2).
以下G行，每行包含2个整数X,Y，(2<=X,Y<=K+1)表示FGD想要在游览城市Y之前,一定要游览城市X。你可以认为至少存在一种满足所有限制的游览方案。

</div><h2>Output</h2><div class=content>只包含一行，包含一个整数，表示最短的旅行距离。
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>8 15 4<br />
1 2 3<br />
1 3 4<br />
1 4 4<br />
1 6 2<br />
1 7 3<br />
2 3 6<br />
2 4 2<br />
2 5 2<br />
3 4 3<br />
3 6 3<br />
3 8 6<br />
4 5 2<br />
4 8 6<br />
5 7 4<br />
5 8 6<br />
3<br />
2 3<br />
3 4<br />
3 5<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>19<br />
<br />
</span></div><h2>HINT</h2>
			<div class=content><p><img border="0" src="images/1097.jpg"><br />
<br />
上面对应于题目中给出的例子。<br />
</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=1097'>Submit</a>][<a href='problemstatus.php?id=1097'>Status</a>][<a href='bbs.php?id=1097'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
